//
// Created by Administrator on 2021/6/3.
//

#include "stdio.h"

//
//1、顺序查找：在顺序表array[0..n-1]中查找关键字为k的记
//录，无论查找成功或失败，均通过修改seek_seq参数来返
//回依次查找的记录位置的序列，seek_seq数组已包含的元素个
//数等于n；查找成功时返回0，失败时返回-1。函数签名如下：
int seq_search(int array[],int n,int k, int seek_seq[]){
    for(int i = 0;i<n;i++){
        if(array[i] == k){
            seek_seq[i] = i;
            return 0;
        }else{
            seek_seq[i] = i;
        }
    }
    return -1;
}


//2、二分查找：在按照递增顺序排列的有序表array[0..n-1]中进行
//二分查找，查找成功时返回0，失败时返回-1；无论查找成功或失败，均通过修改
//seek_seq参数来返回依次查找的记录位置的序列，seek_seq元素已包含的元素个数等于n。函数签名如下：
int bin_search(int array[],int n,int k, int seek_seq[]) {
    int top = 0;
    int rear = n-1;
    int i = 0;

    while (top<=rear){
        int middle = (top+rear)/2;
        if( k > array[middle] ) {
            top = middle +1;
            seek_seq[i] = middle;
        }else if(k < array[middle] ){
            rear = middle -1;
            seek_seq[i] = middle;
        }else{
            seek_seq[i] = middle;
            return 0;
        }
        i++;
    }
    return -1;

}
void main(){
    int array[] = {1,2,3,4,5,6,7,8,9,10};

    int n = 10;
    int k = 8;
    int seek_seq1[10];
    int seek_seq[10];
    for(int j = 0;j<n;j++){
        seek_seq[j] = -1;

    }
    for(int m = 0;m<n;m++){
        seek_seq1[m] = -1;

    }
    seq_search(array,n,k,seek_seq);
    bin_search(array,n,k,seek_seq1);
    printf("seq_search:\n");
    for(int i = 0;i<n;i++){
        if(seek_seq[i] < 0){
            break;
        }

        printf("%d\n",seek_seq[i]);
    }

    printf("bin_search:\n");
    for(int t = 0;t<n;t++){
        if(seek_seq1[t] < 0){
            break;
        }

        printf("%d\n",seek_seq1[t]);

    }
}
